package pro.softzhang.algo.lc100;

import pro.softzhang.algo.flag.knowledge.KDynamicPlanning;
import pro.softzhang.algo.flag.theme.TPalindrome;

/**
 *
 */
@KDynamicPlanning
@TPalindrome
public class LC132_PalindromePartitioningII {
    public static void main(String[] args) {

    }

    static
    class Solution {
        public int minCut(String s) {
            int len = s.length();
            boolean[][] isPalindromes = new boolean[len][len];
            for (int i = 0; i < len; i++) {
                for (int j = 0; j <= i; j++) {
                    char ch1 = s.charAt(i);
                    char ch2 = s.charAt(j);
                    if(ch1 == ch2 && (i <= j + 1 || isPalindromes[j + 1][i - 1])) {
                        isPalindromes[j][i] = true;
                    }
                }
            }

            int[] dp = new int[len];
            for (int i = 0; i < len; i++) {
                if(isPalindromes[0][i]) {
                    dp[i] = 0;
                } else {
                    dp[i] = i;
                    for (int j = 1; j <= i; j++) {
                        if(isPalindromes[j][i]) {
                            dp[i] = Math.min(dp[i], dp[j - 1] + 1);
                        }
                    }
                }
            }
            return dp[len - 1];
        }
    }
}
